'''
    图抽象数据类型（ADT）定义如下：

        - Graph() 创建一个新的空图。
        - addVertex(vert) 向图中添加一个顶点实例。
        - addEdge(fromVert, toVert) 向连接两个顶点的图添加一个新的有向边。
        - addEdge(fromVert, toVert, weight) 向连接两个顶点的图添加一个新的加权的有向边。
        - getVertex(vertKey) 在图中找到名为 `vertKey` 的顶点。
        - getVertices() 返回图中所有顶点的列表。
        - in 返回 True 如果 `vertex in graph` 里给定的顶点在图中，否则返回False。

    实现图的两个方法是邻接矩阵和邻接表。邻接矩阵主要是一个二维矩阵，行和列存储顶点，对应的值就是线上的权重。但往往这样的矩阵都是稀疏的，存储效率太低了
    第二个方法是邻接表，对每个顶点，用一个字典存储到其他顶点的路径和权重
'''
import sys

# 顶点类
class Vertex:
    def __init__(self,key):
        self.id = key
        self.connectTo = {}
        self.color = 'white'
        self.pred = None
        self.disc = 0
        self.dist = sys.maxsize
        self.fin = 0

    def addNeighbor(self,nbr,weight=0): # 添加一个相连的
        self.connectTo[nbr] = weight

    def setColor(self,color): # 颜色(尚未发现=> 白色 / 已经发现 => 灰色 / 完成探索 => 黑色)
        self.color = color

    def setDistance(self, d):  # 设置距离
        self.dist = d

    def setPred(self, p):  # 前驱顶点
        self.pred = p

    def setDiscovery(self, dtime):  # 发现时间
        self.disc = dtime

    def setFinish(self, ftime):  # 结束时间
        self.fin = ftime

    def getFinish(self):  # 没有用到
        return self.fin

    def getDiscovery(self):  # 没有用到
        return self.disc

    def getPred(self):  # 获得上一个节点
        return self.pred

    def getDistance(self):  # 获取距离
        return self.dist

    def getColor(self):
        return self.color

    # def __str__(self):
    #     return str(self.id) + 'connectedTo：' + str([x.id for x in self.connectTo])

    def getConnections(self):
        return self.connectTo.keys()

    def getId(self):
        return self.id

    def getWeight(self,nar):
        return self.connectTo[nar]

# 图类
class Graph:
    def __init__(self):
        self.vertList = {}
        self.numVertices = 0

    def addVertex(self,key):    # 添加顶点
        self.numVertices = self.numVertices + 1
        newVertex = Vertex(key) # 新建顶点
        self.vertList[key] = newVertex
        return newVertex

    def getVertex(self,key):
        if key in self.vertList:
            return self.vertList[key]
        else:
            return None

    def getVertices(self):
        return self.vertList.keys()

    def addEdge(self,f,t,cost=0):
        if f not in self.vertList:  # f：起始顶点
            nv = self.addVertex(f)
        if t not in self.vertList:
            nv = self.addVertex(t)
        self.vertList[f].addNeighbor(self.vertList[t],cost)

    def __contains__(self, item):
        return item in self.vertList

    def __iter__(self):
        return iter(self.vertList.values()) # value是含有的顶点

if __name__ == '__main__':
    g = Graph()
    # for i in range(6):  #添加了6个顶点
    #     g.addVertex(i)

    # 添加边的关系
    g.addEdge(0,1,5)
    g.addEdge(0,5,2)
    g.addEdge(1,2,4)
    g.addEdge(2,3,9)
    g.addEdge(3,4,7)
    g.addEdge(3,5,3)
    g.addEdge(4,0,1)
    g.addEdge(5,4,8)
    g.addEdge(5,2,1)

    # V是图中含有的顶点，w是顶点的connectTo字典中的键值，即它所连的顶点。v.connectTo[w]可以取出键值对应的权重
    for v in g: # 这个返回的是键值：顶点
        for w in v.getConnections():
            print('(%s,%s,%s)' %(v.getId(),w.getId(),v.connectTo[w]))

